package com.vint.lintcode;

import com.vint.common.ListNode;

/**
 * 找出环链表的入口
 */
public class Lintcode103 {
	public ListNode detectCycle(ListNode head) {
		ListNode first = head;
		ListNode meetNode = hasCycle(first);
		if (null == meetNode) {
			return null;
		}
		ListNode second = head;
		first = meetNode;
		while(second != first) {
			first = first.next;
			second = second.next;
		}
		return second;
	}

	public ListNode hasCycle(ListNode head) {
		if (null == head) {
			return head;
		}
	    ListNode first = head;
		if (head.next == head) {
		    return head;
        }
        if (null == head.next) {
		    return null;
        }
        first = head.next;
        ListNode two = head.next.next;
		while(null != first && null != two) {
		    if (first == two) {
		        return first;
            }
            first = first.next;
		    if (null == two.next) {
		        return null;
            }
            two = two.next.next;
		}
		return null;
	}

	public static void main(String[] args) {
	    ListNode head = new ListNode(0);
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        head.next = head1;
        head1.next = head2;
        head2.next = head3;
        head3.next = head1;
        Lintcode103 lintcode103 = new Lintcode103();
        System.out.println(lintcode103.detectCycle(head).val);
	}
}
